﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils.Backtracers;

namespace Algoritmia.Problems.TextProcessing
{
    public class TextSegmenter
    {
        private readonly IMap<string, double> _probabilities;
        private readonly Func<IEnumerable<KeyValuePair<int,int>>,IBacktracer<int, string>> _createBacktracer;

        public TextSegmenter(IMap<string, double> probabilities, Func<IEnumerable<KeyValuePair<int, int>>, 
            IBacktracer<int, string>> createBacktracer = null)
        {
            _probabilities = probabilities;
            _createBacktracer = createBacktracer ?? (back => new DynamicBacktracer<int, string>(back));
        }

        public double Probability(string t)
        {
            var P = new[] {1.0}.Concat(Enumerable.Repeat(0.0, t.Length)).ToArray();
            for(int j = 1; j <= t.Length;j++)
            {
                P[j] = Enumerable.Range(0, j).Select(i => P[i]*_probabilities.Get(t.Substring(i, j-i),0.0)).Max();
            }
            return P[t.Length];
        }

        public string Segment(string t)
        {
            var P = new[] { 1.0 }.Concat(Enumerable.Repeat(0.0, t.Length)).ToArray();
            var back = new int[t.Length+1];
            back[0] = 0;
            for (int j = 1; j <= t.Length; j++)
            {
                P[j] = P[0]*_probabilities.Get(t.Substring(0,j),0.0);
                back[j] = 0;
                for (int i = 1; i < j; i++ )
                {
                    double r = P[i]*_probabilities.Get(t.Substring(i, j-i), 0.0);
                    if ( r > P[j])
                    {
                        P[j] = r;
                        back[j] = i;
                    }
                }
            }
            var backtracer = _createBacktracer(back.Select((e, i) => new KeyValuePair<int, int>(i, e)));
            return string.Join(" ", backtracer.Backtrace(t.Length, (j, bp) => t.Substring(bp[j], j-bp[j])));
        }
    }
}
